from utils.log import Log
from utils.bit_op import BitOp
from utils.profile import Profile


class NQueue(Log):
    # https://www.bilibili.com/video/BV1gr4y1R79Z/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
    def __init__(self, n=4):
        super(NQueue, self).__init__()
        self.n = n
        self.limit = (1 << n) - 1

    @Profile(log=True)
    def total(self):
        if self.n < 1:
            return 0
        return self.f(0, 0, 0)

    def f(self, col, left, right):
        if col == self.limit:
            return 1
        ban = col | left | right
        candidate = self.limit & (~ban)

        ans = 0
        while candidate:
            position = BitOp.right_most_1bit(candidate)
            candidate ^= position
            ans += self.f(col | position, (left | position) >> 1, (right | position) << 1)

        return ans


if __name__ == '__main__':
    # n = 13 total: 73712, time: ~1.5s
    # n = 14 total: 365596, time: ~8.5s
    # n = 15 total: 2279184, time: ~55s
    # 再大就完全不适合用Python
    print(NQueue(14).total())
